package com.fosss.dynamic;

/**
 * 动态规划解决背包问题
 */

public class Bag {
    public static void main(String[] args) {
        int[] w={1,4,3};//物品的重量
        int[] value={1500,3000,2000};//物品的价值
        int m=4;//背包的容量
        int n=value.length;//物品的个数

        //表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值
        //表示前i个物品能够装入容量为j的背包的最大价值
        int[][] v=new int[n+1][m+1];

        //设置第一行和第一列为0，可以不进行设置，因为默认为零
        for (int i = 0; i < v.length; i++) {
            v[i][0]=0;
        }
        for(int i=0;i<v[0].length;i++){
            v[0][i]=0;
        }

        //进行动态规划处理
        for(int i=1;i<v.length; i++){//因为第一行第一列均为零，所以不做处理

            for(int j = 1; j< v[0].length; j++){
                if(w[i-1]>j){//当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
                    v[i][j]=v[i-1][j];
                }else {//当准备加入的新增的商品的容量小于等于当前背包的容量

                    //v[i-1][j] 如果不选当前商品，则使用上一个背包的最大价值
                    // 如果选择了当前商品，则使用value[i-1]+v[i-1][j-w[i-1]])表示当前商品的价值加上背包容量减去当前商品体积后所剩容量所能装的最大价值
                    // value[i-1] :表示当前商品的价值 v[i-1][j-w[i]] ： 装入 i-1 商品，到剩余空间 j-w[i-1]的最大值
                    v[i][j]=Math.max(v[i-1][j],value[i-1]+v[i-1][j-w[i-1]]);
                }
            }
        }

        for (int[] ints : v) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
    }
}




















